package com.ftg.learn.day05.ex;

import java.util.Arrays;

/**
 * 练习排序 问题
 *
 * @author 布衣
 */
public class Question01 {

    /**
     * 排序 : 交换排序   非交换
     * 冒泡排序  ：升序
     */
    public void bubblingSortByAsc(int[] arr) {
        for (int i1 = 0; i1 < arr.length; i1++) {
            for (int i = 0; i < arr.length - 1 - i1; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    /**
     * 冒泡排序  ： 降序
     *
     * @param arr 数组
     */
    public void bubblingSortByDesc(int[] arr) {
        for (int i1 = 0; i1 < arr.length; i1++) {
            for (int i = 0; i < arr.length - 1 - i1; i++) {
                if (arr[i] < arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    /**
     * 选择排序
     *
     * @param arr
     */
    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int max = 0;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[max]) {
                    max = j;
                }
            }
            swap(arr, max, arr.length - 1 - i);
        }
    }

    /**
     * 插入排序
     * @param arr
     */
    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int shu = arr[i];
            for (int j = i - 1; j >= 0 && arr[j] > shu; j--) {
                arr[j + 1] = arr[j];
                arr[j] = shu;
            }
        }
//            int shu = arr[i];
//            for (int j = i - 1; j >= 0 && arr[j] > shu; j--) {
//                if (arr[j] > shu) {
//                    arr[j + 1] = arr[j];
//                    arr[j] = shu;
//                } else {
//                    break;
//                }
//            }

    }

    /**
     * 交换
     *
     * @param arr 数组
     * @param i   第一个下标
     * @param j   第二个下标
     */
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 最大值
     *
     * @param arr 数组
     * @return int
     */
    public int getMax(int[] arr) {
        int max = 0;
//        o(n/2)
        for (int i = 0, len = arr.length - 1; i < len; i++, len--) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[len] > max) {
                max = arr[len];
            }
        }
        return max;
    }

    /**
     * 二分查找法
     * @param arr 数组
     * @param target 目标
     * @return  true
     */
    public boolean binarySearch(int[] arr, int target) {
        int begin = 0;
        int end = arr.length - 1;
        while (begin <= end) {
            int middle = (begin + end) >>> 1;
            if (arr[middle] == target) {
                return true;
            } else if (arr[middle] > target) {
                end = middle - 1;
            } else {
                begin = middle + 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {10, 11, 12, 4, 9, 7, 6, 5, 8};
        Question01 q01 = new Question01();
        q01.selectSort(arr);
        System.out.println(Arrays.toString(arr));
        boolean b = q01.binarySearch(arr, 9);
        System.out.println(b);


        //数据帮助类 Arrays [2,7) >=2 <7
        Arrays.sort(arr,2,7);

        Arrays.fill(arr,11);



        System.out.println(Arrays.toString(arr));
//
//        Question01 q01 = new Question01();
//
//        //插入
//        System.out.println("插入");
//        q01.insertSort(arr);
//        System.out.println(Arrays.toString(arr));
//
//        //选择排序
//        q01.selectSort(arr);
//        System.out.println(Arrays.toString(arr));
//
//        //最大值
//        System.out.println(q01.getMax(arr));
//
//        //升序
//        q01.bubblingSortByAsc(arr);
//
//        //把数组进行直接输出
//        System.out.println(Arrays.toString(arr));
//
//        //降序
//        q01.bubblingSortByDesc(arr);
//
//        //把数组进行直接输出
//        System.out.println(Arrays.toString(arr));

    }

}
